Online Caching Networks with Advers
Online Caching Networks with Adversarial Guarantee
2022 年 12 月 5 日
0:17
1 Introduction
本文研究，任意拓扑结构的网络缓存，内容以对抗性的方式到达。请求到达指定服务器后，可以被指定服务器永久储存。请求也可以由驻留在中间节点处的有限容量的高速缓存提供服务。响应通过相同的路径返回到每个请求的源，从而产生开销。我们的目标是提出一个分布式的、在线的算法，当请求的项目和它们所遵循的路径都被不利地选择时，以最小化后悔的方式确定缓存内容。
这个问题的离线版本是 NP- 难的，但允许（1 − 1/𝑒）多项式时间近似算法。Ioannidis 和 Yeh 提出了一种分布式 Robbins Monro 型算法，该算法在假设随机、平稳请求到达的情况下实现了相同的近似保证。该模型已经激发了几种变体，其中大部分集中于离线和/或静态随机版本的问题。缓存领域的另一个近期研究探索了带有对抗性保证的缓存算法，这些工作的大部分集中于单个高速缓存或简单的二分网络拓扑。
本文的主要目的是将对抗性担保引入到 Ioannidis 和 Yeh 提出的一般网络模型中。这与现有的无遗憾高速缓存设置研究截然不同，这是由于我们模型的分布式特性和网络拓扑的通用性。我们的目标不能通过在线凸优化的技术直接优化以获得次线性后悔。
我们做出了以下贡献：
1.我们从对抗的角度重新审视 Ioannidis 和 Yeh 的一般缓存网络设置
2.我们提出了 DistributedTGOnline，这是一个分布式的在线算法，当不考虑高速缓存更新成本时，对离线方案（与最优构成（1 − 1/𝑒）- 逼近）达到了根号 T 的后悔。
3.我们还扩展了我们的算法以考虑更新成本，我们证明了依然能达到根号 T 的后悔。我们用耦合的缓存决策替代了轮轮独立的缓存决策，通过求解最优运输问题来实现
4.我们使用非平稳需求的实验，包括合成数据和追踪数据，与其他相关算法对比，广泛评估了我们算法的表现，
2.related work
我们的工作基于一个 TGOnline 算法，解决的是在线指派问题。在这个算法中，次模奖励函数以在线的方式到达，在线分配问题的目标是产生一个分配使得遗憾最小。这个算法最终实现了 1-1/e 范围内的遗憾。
除了上述工作外，我们同时考虑了缓存网络设计问题的目标和约束。1.我们证明了 TGOnline 在应用于该问题时，允许分布式实现。2.我们加入了更新成本，之前那没有考虑。
在我们的设置中，在我们的环境中，TGOnline 的直接、幼稚的实现要求（在处理每个请求时）在所有缓存之间进行通信；相比之下，DistributedTGOnline 把通信限制在请求路径上的节点之间。作为一项额外的技术，我们利用了 TGOnline 算法中的一个适应步骤，即颜色洗牌，实际上可以以较低的频率发生。后者在考虑代价更新时对于边界后悔是必要的：在没有这种调整的情况下，TGOnline 算法在考虑更新代价时获得了线性后悔。
3.model
跟着他们的模型，我们考虑一个缓存网络从一个固定的目录中存储事务。节点产生对这些事务的请求，路由到指定的服务器。中间节点可以缓存项目，从而提前服务这些请求。我们从他们的模型出发，假设请求是对抗的，而不是随机的。